public class Code2 {
    // 下降路径最小和(可以从三个方向下降)

    public int minFallingPathSum(int[][] matrix) {
        // 1、创建 dp 表
        // 2、初始化
        // 3、填表
        // 4、返回值

        // 这里创建的 dp 表需要上面多添加一行，左右各多添加一列
        int n = matrix.length;
        int[][] dp = new int[n + 1][n + 2];

        // 初始化操作
        // 这里要求第一行为 0 第一列和最后一列的位置为 正无穷大
        for(int i = 1; i <= n; i++){
            dp[i][0] = dp[i][n + 1] = Integer.MAX_VALUE;
        }

        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                // 这里分为三部分
                // 分别从左上、中间、右上 得到数据
                dp[i][j] = Math.min(dp[i - 1][j],Math.min(dp[i - 1][j - 1],dp[i - 1][j + 1])) + matrix[i - 1][j - 1];
            }
        }

        // 这里返回的是数组最后一行中的最小值
        int ret = Integer.MAX_VALUE;
        for(int j = 1; j <= n; j++){
            ret = Math.min(ret,dp[n][j]);
        }
        return ret;
    }
}
